package com.salim.leetcode.$105;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
    //用先根和中根构造树
    //先遍历先根 第一个肯定是根节点
    //找到中根数组中的那个节点 节点左边是他的左树 右边是他的右树
    //遍历先根数组 找到第一个在左范围内的点为root递归左树
    //遍历先根数组 找到第一个在右范围内的点为root递归右树
    //方法1 维护一个剩余先根列表 有点慢
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        List<Integer> remainPre = new ArrayList<>();
//        for(int i=0;i<preorder.length;i++){
//            remainPre.add(preorder[i]);
//        }
//        return loop(preorder,inorder,remainPre,0,inorder.length-1);
//    }
//
//    public TreeNode loop(int[] preorder, int[] inorder,List<Integer> remainPre,int inStart,int inEnd) {
//        if(inStart>inEnd||inStart<0||inEnd<0||inStart>=inorder.length||inEnd>=inorder.length){
//            return null;
//        }
//
//        for(int j=0;j<remainPre.size();j++){
//            for(int i=inStart;i<=inEnd;i++){
//                if(inorder[i]==remainPre.get(j)){
//                    TreeNode result = new TreeNode(remainPre.get(j));
//                    remainPre.remove(j);
//                    result.left = loop(preorder,inorder,remainPre,inStart,i-1);
//                    result.right = loop(preorder,inorder,remainPre,i+1,inEnd);
//                    return result;
//                }
//            }
//        }
//
//        return null;
//    }

    //方法二 维护指针 这个方法并不到位 还能优化
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return loop(preorder,inorder,0,0,inorder.length-1);
    }

    public TreeNode loop(int[] preorder, int[] inorder,int preStart,int inStart,int inEnd) {
        if(inStart>inEnd||inStart<0||inStart>=inorder.length ||preStart>=preorder.length){
            return null;
        }
        if(inStart==inEnd){
            return new TreeNode(inorder[inStart]);
        }

        for(int i=inStart;i<=inEnd;i++){
            if(inorder[i]==preorder[preStart]){
                TreeNode result = new TreeNode(preorder[preStart]);
                result.left = loop(preorder,inorder,preStart+1,inStart,i-1);
                //i-inStart表示左树的长度 先根的顺序是 根-左-右 所以右根一定出现在根-左之后
                result.right = loop(preorder,inorder,preStart+i-inStart+1,i+1,inEnd);
                return result;
            }
        }

        return null;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
